'''
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
'''
from typing import List, Optional

from c06_tree.utils import TreeNode, built_tree_by_complete_tree, leveloder


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def build(i, j, k, l):
            if i > j:
                return None
            root = TreeNode(preorder[i])
            mid = k
            for p in range(k, l + 1):
                if preorder[i] == inorder[p]:
                    mid = p
                    break
            # 0, 1, 2, mid, 4, 5, 6
            left_size, right_size = mid - k, l - mid
            root.left = build(i + 1,    i + 1 + left_size - 1,
                              k,        mid - 1)
            root.right = build(i + 1 + left_size - 1 + 1,   j,
                               mid + 1, l)
            return root

        return build(0, len(preorder) - 1, 0, len(inorder) - 1)


preorder = [3,9,20,15,7]
inorder  = [9,3,15,20,7]
root = Solution().buildTree(preorder, inorder)
leveloder(root)